package com.example.origin.demo.suanfa.leecode;

public class No21MergeTwoSortedLists {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode next = new ListNode(2);
        listNode.next = next;
        ListNode next1 = new ListNode(3);
        next.next = next1;
        ListNode next2 = new ListNode(4);
        next1.next = next2;
        ListNode next3 = new ListNode(7);
        next2.next = next3;

        ListNode listNode2 = new ListNode(5);
        ListNode next5 = new ListNode(6);
        listNode2.next = next5;


        ListNode node = mergeTwoLists2(listNode2, listNode);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }

        System.out.println();
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哑节点作为新链表的头节点，这样可以简化合并过程中的指针操作
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        // 使用while循环遍历两个链表直到其中一个为空
        while (l1 != null && l2 != null) {
            // 如果l1的值小于等于l2，则将l1节点添加到新链表中，并移动l1指针
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                // 否则将l2节点添加到新链表中，并移动l2指针
                current.next = l2;
                l2 = l2.next;
            }
            // 不管是添加了l1还是l2，current都要向后移动一位
            current = current.next;
        }

        // 当其中一个链表遍历完之后，将另一个未完成的链表剩余部分添加到新链表后面
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // 返回合并后的新链表的头节点（即dummyHead的下一个节点）
        return dummyHead.next;
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        // 创建一个哑节点作为新链表的头节点，这样可以简化合并过程中的指针操作
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        while (l1!=null&&l2!=null){
            if (l1.val<l2.val) {
                current.next = l1;
                l1 = l1.next;
            }else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        if (l1!=null){
            current.next = l1;
        }else {
            current.next = l2;
        }

        // 返回合并后的新链表的头节点（即dummyHead的下一个节点）
        return dummyHead.next;
    }



}
